package string

func FindWords(board [][]byte, words []string) []string {
	var ret []string
	for _, word := range words {
		if FindWord(board, word) {
			ret = append(ret, word)
		}
	}

	return ret
}

func FindWord(board [][]byte, word string) bool {
	n, m := len(board), len(board[0])

	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, m)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if dfs(i, j, board, word, visited) {
				return true
			}
		}
	}

	return false
}

func dfs(i, j int, board [][]byte, word string, visited [][]bool) bool {
	if !visited[i][j] && board[i][j] == word[0] {
		if len(word) == 1 {
			return true
		}

		visited[i][j] = true
		sub := word[1:]

		if i > 0 && dfs(i-1, j, board, sub, visited) {
			return true
		}
		if j > 0 && dfs(i, j-1, board, sub, visited) {
			return true
		}
		if i < len(board)-1 && dfs(i+1, j, board, sub, visited) {
			return true
		}
		if j < len(board[0])-1 && dfs(i, j+1, board, sub, visited) {
			return true
		}

		visited[i][j] = false
	}

	return false
}
